#!/usr/bin/env python
import wx
import operator
from wx import Rect, Point, Size

North, West, South, East = range(4)
g_dirNames = ['N', 'W', 'S', 'E']

class Widget:
    def __init__(self, id, rect):
        self.id = id
        self.rect = rect
    def __str__(self):
        return 'Widget(id=%d, xywh=[%d, %d, %d, %d])' % (self.id, self.rect.x, self.rect.y, self.rect.width, self.rect.height)

def RectCenter(rect):
    return Point(rect.x+rect.width/2, rect.y+ rect.height/2 )

def MakeRectPointSize(pt, sz):
    return Rect(pt.x, pt.y, sz.width, sz.height)
    
def MakeRectPointPoint(A,B):
    x1 = min(A.x, B.x)
    x2 = max(A.x, B.x)
    y1 = min(A.y, B.y)
    y2 = max(A.y, B.y)
    return Rect(x1,y1, x2-x1, y2-y1)

def MakeRect(A, B):
    if isinstance(A, Point) and isinstance(B, Size):
        return MakeRectPointSize(A,B)
    if isinstance(A, Point) and isinstance(B, Point):
        return MakeRectPointPoint(A,B)


def ReverseDir(dir):
    rev = [South, East, North, West]
    return rev[dir]
    
def BFS(root, func=None):
    """ Breadth-First Search with filter function"""
    queue = []
    queue += root.child
    while queue:
        node = queue.pop(0)
        if func is None or func(node):
            yield node
        queue += node.child

def DFS(root, func=None):
    """ Depth-First Search with filter function"""
    stack = []
    stack += root.child[::-1]
    while stack:
        node = stack.pop()
        if func is None or func(node):
            yield node
        stack += node.child[::-1]

class TreeNode:
    def __init__(self, parent=None, symbols=[]):
        self.symbol = symbols
        self.child = []
        self.parent = parent
        self.killed = False
        
        if len(self.symbol)>0 and isinstance(self.symbol[-1], list):
            sym = self.symbol.pop(-1)
            assert( count_if(self.symbol, lambda x: isinstance(x,list)) ==0 )
            if len(sym) == 0:
                return
            elif len(sym) == 1:
                self.symbol.append( sym[0] )
                return
            else:
                self.symbol.append('+')            
                for x in sym:
                    subnode = TreeNode(self, [x])
                    self.child.append(subnode)
        
        
    def IsLeaf(self):
        return len(self.child) == 0
    def IsEnded(self):
        return isinstance(self.symbol[-1], Motion)
    def IsRoot(self):
        return self.parent is None
    
    def GetLastSymbol(self):
        return self.symbol[-1]
    LastSymbol = property(GetLastSymbol)
    
    def GetDiagram(self):
        for x in self.symbol:
            if isinstance(x, int):
                return x
        return None
    Diagram = property(GetDiagram)


    def GetDirection(self):
        for x in self.symbol:
            if isinstance(x, Motion):
                return x.dir
        return None
    Direction = property(GetDirection)
    
    def GetOperator(self):
        for x in self.symbol:
            if x in ['*','+']:
                return x
        return None
    Operation = property(GetOperator)
    
    def IsFormalFormat(self):
        return len(self.symbol) >= 2 and \
            isinstance(self.symbol[0], int) and isinstance(self.symbol[1], Motion)
                
    def __str__(self):
        return 'Node[%s]'% ''.join(map(str, self.symbol))
    #def GetRect(self, diagramList):
    #    dgId = self.Diagram
    #    return find_if(diagramList, lambda dg: dg.id == dgId).rect
    #def GetMovedRect(self, diagramList, subNode):
    #    dgId = self.Diagram
    #    index = self.symbol.index(dgId)
    #    motion = self.symbol[index+1]
    #    if not isinstance(motion, Motion):
    #        motion = subNode.symbol[0]
    #    rect = find_if(diagramList, lambda dg: dg.id == dgId).rect
    #    return motion.ApplyOnRect(rect)
        
    def SymbolPath(self):
        node = self
        symList = []
        while not node.IsRoot():
            symList += node.symbol[::-1]
            node = node.parent
        symList.reverse()        
        return filter(lambda x: not isinstance(x,str), symList)
    

class Motion:
    #Motion Vector
    def __init__(self, dir, scalar):
        self.dir = dir
        self.scalar = scalar
    def ApplyOnPoint(self, pt):
        if self.dir == North:
            return Point(pt.x, pt.y - self.scalar)
        elif self.dir == West:
            return Point(pt.x - self.scalar, pt.y)
        elif self.dir == East:
            return Point(pt.x + self.scalar, pt.y)
        elif self.dir == South:
            return Point(pt.x, pt.y + self.scalar)
    def ApplyOnRect(self, rect):
        return MakeRect( self.ApplyOnPoint(rect.position), rect.Size)

    
    def __str__(self):
        return g_dirNames[self.dir]
    def __repr__(self):
        return '(%s,%d)' % (g_dirNames[self.dir], self.scalar)
        
    def Merge(self, motion):
        assert(self.dir == motion.dir)
        self.scalar = max(self.scalar, motion.scalar)
        

def PosAfterMoved(acter, reacter, dir):
    assert (isinstance(acter, Rect ))
    assert (isinstance(reacter, Rect ))
    assert (acter.Intersects(reacter) )
    if dir == North:
        return Rect(reacter.x,  acter.y - reacter.height, reacter.width, reacter.height)
    elif dir == West:
        return Rect(acter.x -reacter.width, reacter.y, reacter.width, reacter.height)
    elif dir == South:
        return Rect(reacter.x, acter.y + acter.height, reacter.width, reacter.height  )
    elif dir == East:
        return Rect(acter.x +acter.width, reacter.y, reacter.width, reacter.height )
    return None

def GetMotion(acter, reacter, dir):
    assert (isinstance(acter, Rect ))
    assert (isinstance(reacter, Rect ))
    assert (acter.Intersects(reacter) )
    if dir == North:
        return Motion(North,  reacter.y - ( acter.y - reacter.height) )
    elif dir == West:
        return Motion(West, reacter.x - (acter.x -reacter.width))
    elif dir == South:
        return Motion(South, acter.y + acter.height-reacter.y  )
    elif dir == East:
        return Motion(East, acter.x +acter.width-reacter.x)
        
def GetMotion2(dir, posOffset):
    if posOffset.x > 0 and posOffset.y == 0:
        assert(dir == East)
        return Motion(East, posOffset.x)
    elif posOffset.x < 0 and posOffset.y == 0:
        assert(dir == West)
        return Motion(West, -posOffset.x)
    elif posOffset.x == 0 and posOffset.y > 0:
        assert(dir == South)
        return Motion(South, posOffset.y)
    elif posOffset.x == 0 and posOffset.y < 0:
        assert(dir == North)
        return Motion(North, -posOffset.y)
    raise 'invalid argument posOffset'
        

        
def Swap(sequence, i, j):
    sequence[i], sequence[j] = sequence[j], sequence[i]

def SubList(ls, filterFunc):
    for x in ls:
        if filterFunc(x):
            yield x

def remove_if(ls, filterFunc):
    removeList = []
    for i,x in enumerate(ls):
        if filterFunc(x):
            removeList.append(i)
    removeList.reverse()
    for index in removeList:
        del ls[i]
    
def find_if(ls, filterFunc):
    for x in ls:
        if filterFunc(x):
            return x
def count_if(ls, filterFunc):
    cnt = 0
    for x in ls:
        if filterFunc(x):
            cnt+=1
    return cnt
    
INFINITY = 256

def MergeRepeated(evaList):
    retList = []
    for x in evaList:
        merged = False
        for y in retList:
            if x.id == y.id and x.motion.dir == y.motion.dir :
                x.motion.Merge(y.motion)
                merged=True
                break
        
        if not merged:
            retList.append(x)
            
    return retList

def TreeToInfix(root):
    ''' Express tree as infix notation. root must have child field.
    '''
    stack = []
    ret_str = ''
    
    class Node:
        def __init__(self, x, visit):
            self.node = x
            self.visit = visit
    def IsLeaf(x):
        return (len(x.child)==0 )
    def push(x, visit=0):
        stack.append(Node(x, visit))
    def pop(x):
        x = stack.pop()
        return (x.node, x.visit)
        
    push(root)
    while stack is not []:
        node, visit = pop()
        
        if not IsLeaf(node) and visit==0:
            if node is not root:
                ret_str += '('
            push( node, 2 )
            push( node.child[-1] )
            for i in range(-2, -n-1, -1):
                push(node, 1)
                push(node.child[i])
        elif IsLeaf(node) or visit==1:
            ret_str += str(node)
        elif visit==2:
            ret_str += ')'
    
    return ret_str

class DiagramMotion:
    def __init__(self, node):
        self.id = node.symbol[0]
        self.motion = node.symbol[1]
        assert(isinstance(self.id, int))
        assert(isinstance(self.motion, Motion))
        
    

def DiagramKinetimaTreeToInfix(root):
    ''' Express tree as infix notation. root must have child field.
    '''
    stack = []
    ret_str = ''
    
    class Node:
        def __init__(self, x, visit):
            self.node = x
            self.visit = visit
    def IsLeaf(x):
        return (len(x.child)==0 )
    def push(x, visit=0):
        stack.append(Node(x, visit))
    def pop():
        x = stack.pop()
        return (x.node, x.visit)
    def SymbolListToStr(symlist):
        return ''.join( map(str, symlist))
        
    push(root)
    while stack :
        node, visit = pop()
        
        if not IsLeaf(node) and visit==0:
            if node is not root:
                if len(node.child) == 1:
                    assert(node.symbol[-1] not in ['*','+'])
                    prefixSymbol = SymbolListToStr(node.symbol)
                    ret_str += '(%s-' % prefixSymbol
                else:
                    assert(node.symbol[-1] in ['*','+'])
                    prefixSymbol = SymbolListToStr(node.symbol[0:-1])
                    ret_str += '%s(' % prefixSymbol
            
            push( node, 2 )
            childCount = len(node.child)
            push( node.child[childCount-1] )
            for i in range(childCount-2, -1, -1):
                push(node, 1)
                push(node.child[i])
        elif IsLeaf(node):
            ret_str += SymbolListToStr(node.symbol)
        elif visit==1:
            assert(node.symbol[-1] in ['*','+'])
            infixSymbol = str(node.symbol[-1])
            ret_str += infixSymbol
        elif visit==2:
            if node is not root:
                ret_str += ')'
    
    return ret_str
        
def GetEvacuateList(inDg, diagramList, boundary):
    """
    inDg: inserted diagram
    diagramList: a list of diagrams
    """  
    root = TreeNode(None,[])
    coveredDiagrams = [dg.id for dg in diagramList if dg.rect.Intersects(inDg.rect)]
    if not coveredDiagrams:
        return []
                        
    def GetDiagram(id):
        for dg in diagramList:
            if dg.id == id:
                return dg
        
        
    def RemovePathUntilStar(leaf):
        subnode = leaf
        node = leaf.par
        while node is not root:
            if node.LastSymbol == '*':
                node.children.remove(node)
                if len(node.children) == 1:
                    node.symbols.pop()
                return
            subnode = node
            node = node.parent
        node.children.remove(subnode)
    
    def SelectBestChild(childList):
        assert(childList)
        if len(childList)==1:
            return childList[0]
            
        def DgList(subtree):
            for nodes in DFS(subtree):
                yield node.Diagram
                
        def DgListLen(subtree):
            return len([DgList(subtree)])
            
        def Covered(subtree):
            for dg in DgList(subtree):
                if dg in coveredDiagrams:
                    yield dg
        def CoveredLen(subtree):
            return len([Covered(subtree)])
            
        def Curve(subtree):
            curve = 0
            for node in DFS(subtree):
                if node is subtree:
                    continue
                if node.Direction != node.parent.Direction:
                    curve+=1
            return curve
        
        # select covered is maximal and diagram List is minimal
        def child_cmp(A,B):
            return -cmp(CoveredLen(A), CoveredLen(B)) or cmp(DgListLen(A), DgListLen(B)) or cmp(Curve(A), Curve(B))
            
        def IsEndedTree(tree):
            for leaf in DFS(tree, lambda node: node.IsLeaf() ):
                if not leaf.IsEnded():
                    return False
            return True
            
        childList = filter(IsEndedTree, childList)
        assert(childList)
        childList.sort(child_cmp)
        return childList[0]
    
    def KillOtherChild(node, bestChild):
        for child in node.child:
            if child is bestChild:
                continue
            child.parent=None
            child.killed = True
            for x in DFS(child):
                x.killed = True
            
    def MergeUp(leaf):        
        assert(leaf.IsEnded())
        node = leaf.parent
        
        while node is not root:
            print '[MergeUp] node = %s'%node
            assert(node.LastSymbol == '*' or isinstance(node.LastSymbol, int) )
            bestChild = SelectBestChild(node.child)
            print '[MergeUp] bestChild = %s'%bestChild
            KillOtherChild(node, bestChild)
            node.child = [bestChild]
            
            sym = bestChild.symbol.pop(0)
            if node.LastSymbol == '*':
                node.symbol.pop()
            node.symbol.append(sym)                
            if node.IsFormalFormat():
                return
            node = node.parent
            
       
    def SelectBestDirection(motions, parDir):
        assert(motions)
        if len(motions) == 1:
            return motions[0]
        # select same direction as parent node
        if parDir:
            for motion in motions:
                if motion.dir == parDir:
                    return motion
        # select motion with minimal distance
        return min(motions, key=lambda motion:motion.scalar)

    def IsOutOfBound(rect):
        return not boundary.ContainsRect( rect )
        
    def Expand(leaf):
        assert(isinstance(leaf.LastSymbol, int))
        symPath = leaf.SymbolPath()
        print 'symPath(%s)= {%s}'% (leaf, ','.join(map(str,symPath)))
        
        curDg = GetDiagram(symPath[-1])
        if len(symPath)>=3:
            parMotion = symPath[-2]
            parDg = GetDiagram(symPath[-3])
            parRect = parMotion.ApplyOnRect(parDg.rect)
            parId = parDg.id
            parDir = parMotion.dir
        else:
            parRect = inDg.rect
            parId = inDg.id
            parDir = None
        
        
        dirs = [ North, West, South, East]
        if parDir:
            dirs.remove( ReverseDir(parDir) )
            # move direction same as parent.Direction to first priority
            Swap(dirs, 0, dirs.index(parDir))
                
        collisionData = []
        for dir in dirs:
            movedRect = PosAfterMoved(parRect, curDg.rect, dir)
            if IsOutOfBound(movedRect):
                continue
            
            motion = GetMotion2(dir, movedRect.position - curDg.rect.position)
            collided = [dg.id for dg in diagramList if dg.rect.Intersects( movedRect )]
            if curDg.id in collided:
                collided.remove(curDg.id)
            #if parId in collided:
            #    assert (parId not in collided)
            
            collisionData.append( (motion, collided) )
        
        if not collisionData:
            # failed
            RemovePathUntilStar(leaf)
            return
        print 'collisionData(leaf=%s): '%leaf +','.join(map(str, collisionData))
        
        def Cmp_By_CollidedCount(A,B):
            return cmp(len(A[1]), len(B[1]))
        
        collisionData.sort(Cmp_By_CollidedCount)
        zeroResistDirs = [m for m,c in collisionData if len(c)==0]
        numZeroResist = len(zeroResistDirs)
        
        if numZeroResist == 0 :
            if len(collisionData) > 1:
                leaf.symbol.append('*')
            for motion, collided in collisionData:
                node = TreeNode(leaf, [motion, collided ])
                leaf.child.append( node )
        else:
            print 'zeroResistDirs(leaf=%s): '%leaf + ','.join(map(repr, zeroResistDirs))
            motion = SelectBestDirection(zeroResistDirs, parDir)
            leaf.symbol.append( motion )            
    
    
    if len(coveredDiagrams) > 1 :
        root.symbol.append('+')
    
    for id in coveredDiagrams:
        node = TreeNode(root, [id])
        root.child += [node]
    print 'coveredDiagrams: [%s]' % ','.join(map(str, coveredDiagrams))
    
    processed = True
    while processed:
        processed = False
        print 'tree= ' + DiagramKinetimaTreeToInfix(root)
        for leaf in DFS(root, lambda node: node.IsLeaf() and node.IsEnded() and not node.killed ):
            if not leaf.IsFormalFormat():
                MergeUp(leaf)
                processed=True
                
            pertubedDiagrams = [x for x in leaf.SymbolPath() if x in coveredDiagrams ]
            del pertubedDiagrams[0]
            nodesToRemove = filter(lambda node: node.GetDiagram() in pertubedDiagrams, root.child)
            for r in nodesToRemove:
                j = root.child.index(r)
                del root.child[j]
        
        for leaf in BFS(root, lambda node: node.IsLeaf() and not node.IsEnded() and not node.killed  ):
            Expand(leaf)
            processed=True
        
    evaList = [DiagramMotion(node) for node in DFS(root, lambda node: not node.killed)]
    return MergeRepeated(evaList)

